\subsubsection{Solución elegida}

Dada cualquier posición($n,m$) y recorrido ($f(i) \rightarrow (n,m)$, $i$ desde 0 a $NxM-1$) que se desee tomar para completar el tablero,  no es posible a priori tomar decisiones de manera optima, sin contrastarla contra otras soluciones. En el paso $i$ de
la solución que estoy intentando 
no se que cantidad de casilleros libres tendra la solución optima. \\
\\
El método de resolución consistirá en tomar una solución cualquiera y tratar de mejorarla. \\
Se tomo como función de recorrido y punto de comienzo el casillero superior izquierdo del tablero. Cada casillero esta numerado de izquierda a derecha de arriba a abajo (0,0 a 0,M las columnas hacia derecha y 0,0 y 0,n de arriba a abajo). De esta manera se empieza a completar el tablero tomando fichas que encajen con la anterior a izquierda y en caso de estar en una fila 
$>$ 0 con la ficha que este por sobre.\\
Las fichas se las tiene en un contenedor del cual, dada la ficha izquierda y la superior(en caso de no existir estas por borde o por ser blanco se asume que cualquier ficha podrá encajar contra ese lado) se puede extraer una ficha que encaje junto con la cantidad de opciones entre las que se eligió esa ficha. De esta manera se va avanzando, poniendo fichas que encajen en la solución actual. Para cada paso
$i$ en $NxM$ si no se encuentra una ficha se deja un lugar vació y se pasa al siguiente casillero en el orden en que se esta recorriendo la matriz. Al hacer esto se actualiza el contador de casilleros que se dejaron vacíos en esta solución actual y se guarda la posición donde quedo ese casillero vació junto con los otros que se pudieran haber dejado. 
También al poner por primera vez una ficha en un camino dado, se guarda en un vector de $N*M$ la cantidad de opciones que había para el casillero $i$ cuando se decidió poner la ficha  actual. Esto será usado luego para saber cuando en una solución dada, una rama agoto todas las opciones posibles de soluciones. En ese caso será necesario descartar esa subrrama del árbol de soluciones posibles para tomar otra rama.
La primera vez que se trata de completar el tablero, no se tiene una solución a mejorar, con lo cual se van 
eligiendo fichas  que encajen y si no hay se dejan en blanco esos casilleros.  
Para cada casillero en blanco se guardara su respectiva posición 
en la solución construida.
Al llegar al casillero $NxM$ se guarda la cantidad de casilleros dejados en blanco. Ahora se tiene que encontrar una solución que tenga al menos un casillero en blanco menos, para poder mejorar esta solución. Como se guardo cada casillero en blanco, se retrocede hasta el lugar anterior antes del último casillero dejado en blanco y se trata de armar otra permutación que permita llegar al final del tablero con 1 casillero en blanco menos. Si se llega a encontrar esta permutación, se actualiza el contador de casilleros en blanco, para reflejar esta mejor solución y se retrocede nuevamente hasta la posición del ahora último casillero en blanco de la lista  de casilleros en blanco . Asi hasta eventualmente remover todos los casilleros en blanco.
\\
La poda esta dada por  el hecho de que una vez que tengo una solución de K casilleros en blanco, trato de buscar una de k-1 desde la posición  donde puse el último casillero. Cada vez que la única solución es poner un casillero en blanco detengo ese camino y vuelvo atrás por que si estoy en una solución de k-1 casilleros y me quedo sin fichas no puedo seguir por ese camino. 
Los motivos por los que se retrocede en una solución que se esta intentando es por que se deberá poner un casillero en blanco y eso haría que la solución tenga igual cantidad de casilleros que la mejor conocida, o por que para la posición en la que se esta 
se probaron todas las permutaciones posibles de fichas. Con lo que se cambia la ficha anterior  a la actual y se trata de avanzar nuevamente.


\subsubsection{Demostración}

Aclaración: siempre que se diga avanzar o retroceder se refiere a la función $f(i) \rightarrow (n,m)$
que dado un $i$ entre $0$ y $NxM$ recorre el tablero de izquierda a derecha y de arriba a abajo, comenzando en la coordenada $(0,0)$ yendo a la coordenada $(N,M)$  
\\
\\
Sea $Q = <f_{1},,,f_{n}>$  una lista de fichas disponibles y $S = <s_{1},,,s_{n}>$ un vector de longitud $NxM$, 
con $s_{i} \in$ $\mathbb{N}$, e igual a la cantidad de opciones que había en $Q$
al momento ubicar la ficha del paso $i$ de mi solución. \\
\\
Cada vez que se avanza poniendo una ficha el algoritmo registra que en el paso $i$ había $K$ 
fichas que también encajaban en la posición $i$(con $f(i) \rightarrow (n,m)$), colocando $S[i]= s_{i} =K$.\\
Inicialmente $S = <0,0,,,0>$, entonces se ubica la primer ficha(esta puede ser cualquiera) por lo que $s_{0}=NxM$.\\
Al momento de ubicar la ficha del paso $i$, $S$ es de la forma  $S = <s_{1},,,,s_{i-1},,,0>$ y  
cada $s_{t}$ con $t \textless i$ contabilizando la cantidad de opciones que había en el paso $t$ de mi solución. 

\\
\\
Por cada paso $i$ se busca una ficha en $Q$(fichas disponibles) que encaje,
se ubica en el tablero,  se retira de $Q$ y se deja en $S[i]$ la cantidad de fichas \
que había disponibles para encajar en esa posición. \\
En caso de no haber ficha se deja en blanco el casillero y se asigna  1 la cantidad opciones $S[i]$.
De esta manera se llega a completar la totalidad de 
casilleros del tablero en $i = NxM-1$.\\ 
En $NxM$ pasos se llega a una solución(sin saber si es optima todavía).\\ 
Se guardara la cantidad de casilleros blancos que se dejo, así como 
la secuencia de fichas que se coloco en esta solución, que si futuras
soluciones no mejoran será la óptima.
Ahora se empieza el proceso de mejora de la solución encontrada.\\
\\
Desde $i = NxM-1$ a $i = 0$ se devuelve la ficha que se ubico 
en el paso $i$ a $Q$ se asigna $S[i]= S[i]-1$  y se pide una nueva ficha 
a $Q$, ahora se trata de buscar una solución desde $i$ pero con esta nueva ficha. \\

Al momento de llegar a 0 $S[i]$  se retrocede en la solución actual($i = i-1$) dado 
que se probaron todas las posibilidades para esta posición en la solución actual.\\

Si $S[i] > 0$ en la posición $i$  de la solución actual  entonces
se puede avanzar. Se toman fichas de $Q$ y se completa el tablero
junto con $S$, y esto llevara a una nueva solución.  \\
En caso de  $S[i] =0 $  se retrocede a $i-1$, se decrementa $S[i-1] = S[i-1]-1$ 
y se intenta una solución desde esa nueva posición. 

% Se puede ver que esta operatoria es la misma que el de un stack de llamadas recursivas en el caso de 
% que el algoritmo se plantee de manera recursiva.
% \begin{quote}
% \begin{verbatim}
% Buscar(i)
    
%     MejorSolucion = NxM
    
%     Para f entre las fichas de Q que encajan 
%     en el la posición i 

%         Ubicar la ficha f en el tablero
%         if Buscar(i+1) < MejorSolucion
%             MejorSolucion = Buscar(i+1)

%     Return MejorSolucion
% \end{verbatim}
% \end{quote}
% Aca se puede ver la version iterativa del pseudocodigo.
\begin{quote}
\begin{verbatim}
Buscar()

    Tablero
    S[NxM] = <NxM,0,,,0>
    MejorSolucion = NxM
    i  = 1

    mientras i>= 0 
        si i == NxM
            - grabar solucion si es mejor que anteriores en MejorSolucion
            i = i-1 
            continue
        si S[i] = 0
            - buscar ficha en Q que encaje en el 
            tablero en la posicion i

            - S[i] = cantidad de opciones de fichas en Q para la pos i del tablero
            - i = i+1
            - continue 

        S[i] =  S[i]- 1    
        Si S[i] = 0 
            - devolver la ficha en la posicion i a Q
            i = i-1 
            continue
                
        si S[i] > 0            
            - buscar ficha en Q que encaje en el tablero, devolviendo la que estaba en la
            posicion i
            - posicionar la ficha elegida en el tablero
            i = i+1
            continue

    Return MejorSolucion
\end{verbatim}
\end{quote}

En el paso $i$ tengo $S[i]$ subsoluciones posibles para mi solución 
actual.Se puede ver que ubicando fichas de 0 a $NxM-1$
y registrando en el paso $i=NxM-1$ la cantidad de
casilleros blancos que dejo, para poder 
devolver la solución que haya obtenido la menor cantidad de casilleros libres.\\
\\
Optimalidad de la solucion:\\
El algoritmo en cada paso recorre toda la cantidad de fichas que puede
ubicar en esa posicion. Luego avanza a la posicion siguiente 
y prueba con todas las fichas disponibles para la posicion siguiente. 
Una vez que agota la posibilidades en una posicion va a la anterior 
cambia la ficha y vuelve a avanzar. Esto recorre todas las posibles
soluciones hasta la casilla NxM. Dado que en ese momento si 
la solucion es minima se la registra y se esta recorriendo 
todos las posibles soluciones,  entonces se puede ver
que la solucion que se retorna es optima. \\
\\
Las podas implementadas solo eliminan caminos en caso de haber llegado al 
final de una solucion. Al volver al ultimo 
casillero libre colocado y cambiar la ficha anterior a este estoy seguro 
que no elimino soluciones por que si hubiera habido posibilidad de armar
una solucion mejor no se hubiera colocado ese casillero libre. Por lo que 
seguir intentando con la ficha anterior al blanco nunca me va a dar posibilidad
de mejorar la solucion que tengo. Se puede ver que no se recortan soluciones
que posiblemente sean optimas. Solo soluciones que a lo sumo son iguales a una que ya conozco. 
Por lo tanto la poda no altera la optimalidad de la solucion ni la correctitud.

% Sobre el algoritmo recursivo se puede ver haciendo inducción en la cantidad
% de casilleros del tablero que el algoritmo es correcto.
% En el caso de un tablero con 1  casillero y una ficha es trivial.
% Supongamos ahora que el algoritmo resuelve el problema para tableros 
% de $k$ fichas. Me devuelve la solución óptima. 
% Si tengo un tablero de $k+1$ casilleros y retiro una ficha y una casilla  
% puedo resolver ese problema  de $k$ casilleros
% con las $k$ fichas por HI. Ahora si para cada ficha entre las $K+1$  resuelvo
% el problema con $K$ casillas y $K$ fichas(todas menos la que saco), el resultado 
% va a ser optimo en esa instancia. Ahora si entre esos $k+1$ resultados que obtengo de 
% probar con los tableros de tamaño $k$ , busco 
% el que tiene menor cantidad de espacios en blanco y que encaja con la ficha 
% que saque para la posición 0, entonces puedo estar seguro 
% que mi solución para k+1 casilleros es óptima.\\
% \\
% Supongamos que esto no es así que una solución óptima en un tablero de $K$ casillas
% puede llevar a una solución de $K+1$ casillas no óptima. 
% En el paso $K+1$ tomo las $K+1$ sub soluciones y trato de encajar 
% la ficha que saque con las de $K$ siguientes. Si encaja 
% me dejara una cantidad de casilleros libres igual al de la solución de $K$
% casillas, por que no agregue un blanco. Sino serán $+1$ casilleros blancos
% los de mi solución $K+1$, entre todas las posibles soluciones $K+1$ elegí la mejor, 
% pero si supongo que esta solución no es óptima quiere decir que o hay otra de 
% las K+1 que tiene menor cantidad de blancos, cosa que no puede pasar por que 
% elegí el mínimo, o bien existen permutaciones de $K$ casillas mejores
% a las que utilice para pegar mi casilla $K+1$. Pero de  nuevo
% por HI cualquier otra solución de $K$ tiene que tener $\geq$ cantidad
% de casilleros libres que la que utilizo para comparar.
% Luego mi solución $K+1$ es óptima.
